﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习九月份
{
    public class Solution234
    {
        public bool IsPalindrome(ListNode head)
        {
            //快慢指针找中间
            ListNode fast = head;
            ListNode low = head;
            while (fast != null && fast.next != null)
            {
                fast = fast.next.next;
                low = low.next;
            }

            //翻转链表
            ListNode right = Reverse(low);
            Console.WriteLine(right.val);
            ListNode left = head;
            while (left != null)
            {
                if (left.val == right.val)
                {
                    left = left.next;
                    right = right.next;
                }
                else
                {
                    return false;
                }
            }
            return true;
        }

        private ListNode Reverse(ListNode head)
        {
            ListNode dummyHead = new ListNode();

            while (head != null)
            {
                ListNode next = head.next;

                head.next = dummyHead.next;
                dummyHead.next = head;
                head = next;
            }
            return dummyHead.next;
        }
    }
}